// https://www.lintcode.com/problem/one-edit-distance/description
// 640. One Edit Distance
// Given two strings S and T, determine if they are both one edit distance apart.

// Example
// Given s = "aDb", t = "adb"
// return true





class Solution {
public:
    /**
     * @param s: a string
     * @param t: a string
     * @return: true if they are both one edit distance apart or false
     */
    bool isOneEditDistance(string &s, string &t) {
        int m = s.length();
        int n = t.length();
        // 法一：常规
        // int** dis = new int*[m + 1];
        // for (int i = 0; i < m + 1; i++)
        // {
        //     dis[i] = new int[n + 1];
        // }
        // for (int i = 0; i < m + 1; i++)
        // {
        //     dis[i][0] = i;
        // }
        // for (int i = 0; i < n + 1; i++)
        // {
        //     dis[0][i] = i;
        // }
        // for (int i = 1; i < m + 1; i++)
        // {
        //     for (int j = 1; j < n + 1; j++)
        //     {
        //         if (s[i - 1] == t[j - 1])
        //         {
        //             dis[i][j] = dis[i - 1][j - 1];
        //         }
        //         else
        //         {
        //             dis[i][j] = min(min(dis[i - 1][j], dis[i][j - 1]), dis[i - 1][j - 1]) + 1;
        //         }
        //     }
        // }
        // if (dis[m][n] == 1)
        // {
        //     return true;
        // }
        // else
        // {
        //     return false;
        // }
        
        s = s + "0";
        t = t + "0";
        // 法二：直接判断 越界问题？
        // s=“abcd” t=“abce” output: true
        // • s=“abcd” t=“abcef” output: false
        // • 想一想特殊情况：两字符串长度相差太大时？两个字符串长度一样？
        // • 三种情况： 长度差>1 长度差=0 长度差=1
        if (s == t || abs(m -n) > 1)
        {
            return false;
        } else
        {
            int len = min(m, n);
            int i;
            for (i = 0; i < len; i++)
            {
                if (s[i] != t[i])
                {
                    return (s[i + 1] == t[i + 1] || s[i] == t[i + 1] || s[i + 1] == t[i]);
                }
            }
            return true;
        }
        
    }
};